package listbyorder.access001_100.test30;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/5/29 20:29
 */
public class Solution2 {

    // 使用HashMap记录中间值
    // 1 边界条件： 如果words为null或者组成的单词长度大于s的长度，则直接返回空集合list
    // 2 记录map中每个单词出现的次数
    // 3 遍历s，每次遍历一个字符串的长度，如果当前字符串在map中，则将当前的字符串放到一个新的map中去
    // 4 如果新map中当前字符串对应的次数大于之前map中出现的次数，则当前位置不匹配，跳过
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        int w_nums = words.length;
        if (w_nums == 0) return res;
        int w_len = words[0].length();
        if (w_len * w_nums > s.length()) return res;
        // 创建哈希表
        HashMap<String, Integer> w_map = new HashMap<>();
        for (String str : words) {
            int value = w_map.getOrDefault(str, 0);
            w_map.put(str, value + 1);
        }
        for (int i = 0; i + (w_len * w_nums) <= s.length(); i += w_len) {
            HashMap<String, Integer> c_map = new HashMap<>();
            int num = 0;
            while (num < w_nums) {
                String cur = s.substring(i + num * w_len, i + (num + 1) * w_len);
                if (w_map.containsKey(cur)) {
                    int value = c_map.getOrDefault(cur, 0);
                    c_map.put(cur, value + 1);
                    if (c_map.get(cur) > w_map.get(cur)) {
                        break;
                    }
                } else {
                    break;
                }
                num++;
            }
            if (num == w_nums) {
                res.add(i);
            }
        }
        return res;
    }
}
